﻿#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    vector<int> rearrangeBarcodes(vector<int>& b)
    {
        unordered_map<int, int> hash; // 统计每个数出现的频次
        int maxVal = 0, maxCount = 0;
        for (auto x : b)
        {
            if (maxCount < ++hash[x])
            {
                maxCount = hash[x];
                maxVal = x;
            }
        }
        int n = b.size();
        vector<int> ret(n);
        int index = 0;
        // 先处理出现次数最多的那个数
        for (int i = 0; i < maxCount; i++)
        {
            ret[index] = maxVal;
            index += 2;
        }
        // 处理剩下的数
        hash.erase(maxVal);
        for (auto& [x, y] : hash)
        {
            for (int i = 0; i < y; i++)
            {
                if (index >= n) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
};

int main()
{
    vector<int> barcodes = { 1, 1, 1, 1, 2, 2, 3, 3 };

    auto v = Solution().rearrangeBarcodes(barcodes);

    for (auto& e : v) cout << e << " ";

    return 0;
}


